#include <iostream>
#include <cstdlib>
using namespace std;

struct chainNode
{
    /* data */
    int element;
    chainNode *next;

    chainNode() {}
    chainNode(const int &element)
    {
        this->element = element;
        this->next = NULL;
    }
    chainNode(const int &element, chainNode *next)
    {
        this->element = element;
        this->next = next;
    }
};

class chain
{
public:
    chain(int initialCapacity = 10);
    chain(const chain &theChain);
    ~chain();
    int indexOf(const int &theElement) const;
    void insert(const int &theElement);
    chain merge(chain &theChain);
    void output(ostream &out) const;
    friend ostream &operator<<(ostream &out, const chain &x);

protected:
    chainNode *firstNode;
    int listSize;
};

chain::chain(int initialCapacity)
{
    firstNode = NULL;
    listSize = 0;
}

chain::chain(const chain &theList)
{
    listSize = theList.listSize;
    if (listSize == 0)
    {
        firstNode = NULL;
        return;
    }
    chainNode *sourceNode = theList.firstNode;
    firstNode = new chainNode(sourceNode->element);
    sourceNode = sourceNode->next;
    chainNode *targetNode = firstNode;
    while (sourceNode != NULL)
    {
        targetNode->next = new chainNode(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = NULL;
}

chain::~chain()
{
    chainNode *deleteNode;
    while (firstNode != NULL)
    {
        deleteNode = firstNode;
        firstNode = firstNode->next;
        delete deleteNode;
    }
}

int chain::indexOf(const int &theElement) const
{
    int index = 1;
    chainNode *currentNode = firstNode;
    while (currentNode != NULL && currentNode->element != theElement)
    {
        index++;
        currentNode = currentNode->next;
    }
    if (currentNode == NULL)
    {
        return 0;
    }
    else
    {
        return index;
    }
}

void chain::insert(const int &theElement)
{
    chainNode *newNode = new chainNode(theElement);
    chainNode *currentNode = firstNode;
    if (firstNode == NULL)
    {
        firstNode = newNode;
        return;
    }
    if (theElement <= firstNode->element)
    {
        newNode->next = firstNode;
        firstNode = newNode;
    }
    else
    {
        while (currentNode->next != NULL && currentNode->next->element < theElement)
        {
            currentNode = currentNode->next;
        }
        newNode->next = currentNode->next;
        currentNode->next = newNode;
    }
}
chain chain::merge(chain &theChain)
{
    chainNode *p1 = firstNode;
    chainNode *p2 = theChain.firstNode;
    chainNode *p;
    chain theList;
    while (p1 != NULL && p2 != NULL)
    {
        if (theList.firstNode == NULL)
        {
            if (p1->element <= p2->element)
            {
                theList.firstNode = p1;
                p1 = p1->next;
            }
            else
            {
                theList.firstNode = p2;
                p2 = p2->next;
            }
            p = theList.firstNode;
        }
        else
        {
            if (p1->element <= p2->element)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
    }
    if (p1 != NULL)
    {
        while (p1 != NULL)
        {
            p->next = p1;
            p = p->next;
            p1 = p1->next;
        }
    }
    if (p2 != NULL)
    {
        while (p2 != NULL)
        {
            p->next = p2;
            p = p->next;
            p2 = p2->next;
        }
    }
    return theList;
}

void chain::output(ostream &out) const
{
    chainNode *currentNode = firstNode;
    for (; currentNode->next != NULL; currentNode = currentNode->next)
    {
        out << currentNode->element << ",";
    }
    out << currentNode->element;
}

ostream &operator<<(ostream &out, const chain &x)
{
    x.output(out);
    return out;
}

int main()
{
    cout << "Input1" << endl;
    int num;
    chain myChain;
    chain p;
    cin >> num;
    while (num != 0)
    {
        myChain.insert(num);
        cin >> num;
    }
    cout << "Output1" << endl;
    cout << myChain << endl;
    cout << "Input2" << endl;
    cin >> num;
    myChain.insert(num);
    cout << "Output2" << endl;
    cout << myChain << endl;
    cout << "Input3" << endl;
    cin >> num;
    cout << "Output3" << endl;
    cout << myChain.indexOf(num) << endl;
    cout << "Input4" << endl;
    cin >> num;
    cout << "Output4" << endl;
    cout << myChain.indexOf(num) << endl;
    cout << "Input5" << endl;
    cin >> num;
    while (num != 0)
    {
        p.insert(num);
        cin >> num;
    }
    cout << "Output5" << endl;
    cout << p << endl;
    cout << myChain.merge(p) << endl;
    cout << "End" << endl;
    system("pause");
    return 0;
}